package arithmetic1.stack;

import java.util.Stack;

/*
    中缀表达式转为后缀表达式:
        1.初始化两个栈，运算符栈s1和存储中间结果的栈s2
        2.从左到右扫描中缀表达式
        3.遇到操作数时，进s2栈
        4.遇到运算符时，比较其与s1栈顶运算符的优先级:
            1.如果s1为空，或者栈顶符号为 ( 那么该运算符进s1栈
            2.否则，如果优先级比s1栈顶元素高，该符号进s1栈
            3.如果优先级比s1栈顶元素优先级低，那么将s1栈顶的运算符弹出压入到s2栈中，再次转到4.1这个步骤开始判断
        5.遇到括号时：
            1.如果是左括号，直接压入s1栈
            2.如果是右括号，则依次弹出s1栈顶的运算符，并且压入s2，直到遇到左括号为止，此时将这一对括号丢弃
        6.重复步骤2-5，直到解析到中缀表达式最右边
        7.将s1剩余的运算符依次弹出，并且压入s2
        8.依次弹出s2中的元素并且输出，结果的逆序就是该中缀表达式的后缀表达式
 */
public class InfixToSuffix {
    public static void main(String[] args) {
        //定义一个中缀表达式,每个操作符之间用空格隔开
        String infix="(3+5)*2-5";       // 3 4 + 2 * 6 -  -->  - 6 * 2 + 4 3
        //将中缀表达式转为后缀表达式
        String suffix=infixToSuffix(infix);
        //解析后缀表达式
        int result = Suffix.parseSuffix(suffix);
        System.out.println("结果为:"+result);
    }

    //当这个字符是运算符时应该进行的操作步骤
    public static void isOperStep(Stack<String> s1,Stack<String> s2,char ch){
        if(s1.empty() || s1.peek().equals("(")){       //符号栈为空或者栈顶元素为(
            //将符号进s1栈
            s1.push(ch+"");
        }else{      //符号栈不为空,并且栈顶元素不为(
            if (priority(ch)>priority(s1.peek().charAt(0))){  //该符号优先级高于s1栈顶符号的优先级
                //将该符号进s1栈
                s1.push(ch+"");
            }else { //该符号优先级小于等于s1栈顶符号的优先级
                //将s1栈顶元素弹出并且压入到s2中，
                String str = s1.pop();
                s2.push(str);
                //再次比较该符号与s1栈顶符号的优先级
                isOperStep(s1,s2,ch);
            }
        }
    }

    //判断入栈的字符是不是操作符
    public static boolean isOperation(int ch){
        return ch=='+' || ch=='-' || ch=='*' || ch=='/' || ch=='(' || ch==')';
    }

    //返回运算符的优先级,数值越大优先级越高
    public static int priority(char ch){
        if(ch=='+' || ch=='-'){
            return 1;
        }else if (ch=='*' || ch=='/'){
            return 2;
        }else if (ch=='(' || ch==')'){
            return 3;
        }else {
            return 0;
        }
    }

    //中缀表达式转为后缀表达式
    public static String infixToSuffix(String infix){
        //定义两个栈
        Stack<String> s1=new Stack<>();
        Stack<String> s2=new Stack<>();
        //定义变量来接收后缀表达式
        String suffix="";
        //用来扫描中缀表达式的指针
        int index=0;
        //用来拼接多位数的变量
        String num="";
        //逐一解析中缀表达式
        while (true){
            if (index>=infix.length()){   //字符串已经解析完毕
                break;
            }
            //从str中取出一个字符来解析
            char ch=infix.charAt(index);
            //判断该字符是运算符还是数字
            if(isOperation(ch)){    //是操作符
                if(ch=='('){     //该操作符是左括号
                    //将左括号压入s1
                    s1.push(""+ch);
                }else if(ch==')'){     //该操作符是右括号
                    //依次弹出s1栈顶的运算符，并且压入s2，直到遇到左括号为止，此时将这一对括号丢弃
                    while (!s1.peek().equals("(")){      //遇到左括号为止
                        //将s1栈顶符号弹出,并压入到s2中
                        String s=s1.pop();
                        s2.push(s);
                    }
                    //将左括号丢弃
                    s1.pop();
                }else{  //该操作符不是括号,是运算符
                    //进行一系列判断操作,用递归函数来完成
                    isOperStep(s1,s2,ch);
                }
            }else{  //是数字
                //拼接多位数
                num+=ch;
                if(index==infix.length()-1){   //当前已经扫描到字符串最后
                    //将num进s2栈
                    s2.push(num);
                    //将num清空
                    num="";
                }else {     //当前没有扫描到字符串最后
                    if(isOperation(infix.charAt(index+1))){ //数字的下一位是符号,直接把该数字进数栈
                        //将num进s2栈,
                        s2.push(num);
                        //将num清空
                        num="";
                    }
                }
            }
            //将指针后移
            index++;
        }
        //字符串解析完毕后，将s1栈的运算符依次弹出，并且压入到s2中
        while (!s1.empty()){
            String s = s1.pop();
            s2.push(s);
        }
        //定义一个temp来接收后缀表达式的逆序
        String temp="";
        //依次弹出s2中的元素并且输出，结果的逆序就是该中缀表达式的后缀表达式
        while (!s2.empty()){
            String s = s2.pop();
            s+=" ";
            temp+=s;
        }
        //将temp最后面的空格去掉
        temp=temp.substring(0,temp.length()-1);
        //将temp逆序变成后缀表达式
        for (int i=temp.length()-1;i>=0;i--){
            suffix+=temp.charAt(i);
        }
        return suffix;
    }
}
